public class LinkedLast {
    class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val = val;
        }
    }
    public Node head;
    public void remove(int value){
        if(head == null){
            return ;
        }
        Node prev = head;
        Node cur = head.next;
        while(cur!= null){
            if(cur.val == value){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
            if(head.val==value){
                head = head.next;
            }
        }
    }
    public void addFirst(int data){
        Node node = new Node(data);
        node.next = head;
        head = node;
    }
    public void display(){
        while(head!=null){
            System.out.print(head.val+" ");
            head = head.next;
        }
        System.out.println();
    }
<<<<<<< HEAD
    public void display(LinkedLast.Node NewHead){
        while(NewHead!=null){
            System.out.print(NewHead.val+" ");
            NewHead = NewHead.next;
        }
        System.out.println();
    }
=======
>>>>>>> 3d4de45b752d380e1a8e388eedcda6c0e088661c


    public boolean chkPalindrome() {
        if(head == null){//为空链表的情况
            return false;
        }
        if(head.next == null){//只有一个节点的情况
            return true;
        }
        Node fast = head;
        Node slow = head;
        //1.找中间节点
        while(fast != null && fast.next != null){//两个判断条件的原因时，fast指针不能为空，因为fast定义的时候被赋值为head，若fast为空，则代码报空指针异常，两个判断条件也不能调换顺序
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、 翻转
        Node cur = slow.next;//cur代表当前需要反转的节点
        while(cur != null){
            Node curNext = cur.next;//curNext作为标记，cur节点反转之后，就不会指向cur原本后面的节点，所以用curNext记录.
            cur.next = slow;
            slow = cur;//slow指针向后走
            cur = curNext;//cur也向后走
        }
        //3、一个从前往后，一个从后往前
        while(slow != head){//slow和head走到同一个节点相遇，循环结束
            if(head.val != slow.val){//在循环期间，head.val != slow.val,结束，这个链表不是循环链表
                return false;
            }
            //当链表的节点数为偶数的时候，用此if来判断时偶数节点的情况
            if(head.next == slow){//当存在链表节点数为偶数的情况，head和slow不可能同时走到一个节点上，当两个相邻时，该链表为回文链表。
                return true;
            }
            slow = slow.next;//若两个值相等，则slow往前，head向后
            head = head.next;
        }
        return true;
    }
    public Node partition(int x){
        Node bs = null;
        Node be = null;
        Node as = null;
        Node ae = null;
        Node cur = head;
        while(cur != null){
            if(cur.val < x){
                if(bs == null){//判断是不是第一次插入
                    bs = cur;//是第一次插入bs和be都指向cur
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //有可能<x的部分有节点，>=x部分没节点；也有可能结果相反
        if(bs == null){//如果第一个里面没有节点，那就返回第二个部分
            return as;//如果两个都为空，那么返回的是null,因为as初始赋值为null.
        }
        //第一个部位不为空
        be.next = as;//将两个部分串起来，若as为空，那就表示只有一个部分
        if(as != null){//如果第二个部分不为空，进入将链表的最后一个节点的next置为null
            ae.next = null;
        }
        return bs;//返回新链表的头节点
    }
<<<<<<< HEAD
    public boolean hasCycle() {
        Node fast = head;
        Node slow = head;
        while (fast != null && fast.next != null) {//循环的判断条件是，不论链表的节点是单数还是双数，都要有环，fast == null和fast.next == null表示将链表循环结束
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {//判断两个指针相遇，则返回true，不相遇返回false
                break;
            }
        }
        if(fast == null || fast.next == null){//将链表循环完，没有进入环，说明链表没有环
            return false;
        }
        return true;
    }
    public LinkedLast.Node detectCycle(){
        Node fast = head;
        Node slow = head;
        //1、找相遇点
        while (fast != null && fast.next != null) {//循环的判断条件是，不论链表的节点是单数还是双数，都要有环，fast == null和fast.next == null表示将链表循环结束
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {//判断两个指针相遇，则返回true，不相遇返回false
                break;
            }
        }
        if(fast == null || fast.next == null){//将链表循环完，没有进入环，说明链表没有环
            return null;
        }
        //链表若是有环，将上述代码走完，两个指针相遇。找到相遇点
        slow = head;//slow回到链表的开头
        //2、找入口点
        while(fast != slow){//当两个指针没有再次相遇时
            fast = fast.next;//fast和slow以相同的速度向前挪动，直到再次相遇，找到入环的第一个节点
            slow = slow.next;
        }
        return fast;
    }
=======
>>>>>>> 3d4de45b752d380e1a8e388eedcda6c0e088661c
}
